package main

import "go-leetcode/leetcode/utils"

// 206.反转链表
func main() {
	listNode := utils.GetListNodeByArray([]int{5, 6, 1, 8, 4, 5})
	node := reverseListRecur(listNode)

	pointListNode := listNode
	pointResNode := node
	for pointListNode != nil {
		print(pointListNode.Val, "")
		pointListNode = pointListNode.Next
	}
	println("转换为")
	for pointResNode != nil {
		print(pointResNode.Val, " ")
		pointResNode = pointResNode.Next
	}
	return
}

func reverseListRecur(head *utils.ListNode) *utils.ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	var headPoint *utils.ListNode
	nextPoint := head

	headPoint, nextPoint = recurReverseNode(headPoint, nextPoint)

	return headPoint
}

func recurReverseNode(head *utils.ListNode, next *utils.ListNode) (*utils.ListNode, *utils.ListNode) {
	if next == nil {
		return head, next
	}

	nNext := next.Next
	next.Next = head
	nHead := next

	return recurReverseNode(nHead, nNext)
}

func reverseList(head *utils.ListNode) *utils.ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	pointHead := head
	nextNode := head.Next
	pointHead.Next = nil

	for nextNode != nil {
		nNode := nextNode.Next

		nextNode.Next = pointHead
		pointHead = nextNode

		nextNode = nNode
	}

	return pointHead
}

//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
//
//
//示例 1：
//
//
//输入：head = [1,2,3,4,5]
//输出：[5,4,3,2,1]
//示例 2：
//
//
//输入：head = [1,2]
//输出：[2,1]
//示例 3：
//
//输入：head = []
//输出：[]
//
//
//提示：
//
//链表中节点的数目范围是 [0, 5000]
//-5000 <= Node.val <= 5000
//
//
//进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
